// 大根堆
function buildHeap(arr, len) {
    if(len === 1) return
    for(let i = Math.floor(len / 2); i > 0; i++) {
        heapify(arr, len, i)
    }
}
function heapify(arr, len, i) {
    while(true) {
        let minIndex = i
        if(2 * i <= len && arr[2 * i] < arr[i]) {
            minIndex = 2 * i
        }
        if(2 * i + 1 <= len && arr[2 * i + 1] < arr[minIndex]) {
            minIndex = 2 * i + 1
        }
        if(minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break;
        }
    }
}
function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
class MyHeap {
    constructor(compare) {
      this.arr = []
      this.compare = compare ? compare : (a, b) => a > b
    }
    get size() {
      return this.arr.length
    }
    // 插入元素
    push(num) {
      this.arr.push(num)
      // 向上调整
      this.siftup(this.arr.length - 1)
    }
    // 向上调整
    siftup(index) {
      let {arr, compare, parent} = this
      while(index > 0 && compare(arr[index], arr[parent(index)])) {
        this.swap(index, parent(index))
        index = parent(index)
      }
    }
    // 获得堆顶元素
    pop() {
      if(this.arr.length == 0) return null
      this.swap(0, this.arr.length - 1)
      let n = this.arr.pop()
      this.siftdown(0)
      return n
    }
    // 向下调整
    siftdown(index) {
      let {arr, compare} = this
      while(true) {
        let tempInx = index
        let len = arr.length
        if(2 * index + 1 < len && compare(arr[2 * index + 1], arr[index])) {
          tempInx = 2 * index + 1
        }
        if(2 * index + 2 < len && compare(arr[2 * index + 2], arr[tempInx])) {
          tempInx = 2 * index + 2
        }
        if(tempInx === index) break
        this.swap(tempInx, index)
        index = tempInx
      }
    }
    // 获取父节点
    parent(index) {
      return Math.ceil(index / 2) - 1
    }
    swap(i, j) {
      let temp = this.arr[i]
      this.arr[i] = this.arr[j]
      this.arr[j] = temp
    }
    // 获取堆顶元素
    peek() {
      return this.arr[0]
    }
  }
  